package dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

// 边与边的权
class Edge {
    public int to;
    public int w;

    public Edge(int to, int weight) {
        this.to = to;
        this.w = weight;
    }
}

public class Main {

	
	//最大整数表示无通路
	static int INF = Integer.MAX_VALUE;
	//两点间的路径长度
    static int[] dist;
    //路径点的前序
    static int[] prev;
    //路径点分组
    static boolean[] visited;
    //图——邻接表
    static List<List<Edge>> g = new ArrayList<>();
    
    public static void showGraph() {
    	for(int i=0;i<g.size();i++) {
    		for(int j=0;j<g.get(i).size();j++) {
    			System.out.printf("[f:%d,t:%d,w:%d]",i,g.get(i).get(j).to,g.get(i).get(j).w);
    		}
    		System.out.println();
    	}
    }
    
    public static void dijkstra(int start) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				//dist[o1]大时，返回正数表示o1往后排，升序
				//该优先队列是小顶堆
				return dist[o1] - dist[o2];
			}
        });
        
        pq.offer(start);
        dist[start] = 0;

        while (!pq.isEmpty()) {
            //取出距离start最近的点
            int u = pq.poll();
            visited[u] = true;
            //遍历u的每条边u-v，如果能通过u使得start到v的距离变得更短，更新start到v的距离dist[v]
            for (Edge e : g.get(u)) {
                int v = e.to;
                int weight = e.w;
                if (!visited[v] && dist[v] > dist[u] + weight) {
                    dist[v] = dist[u] + weight;
                    //记录前驱节点
                    prev[v] = u;
                    //将v加入优先队列，下次参与比较距离start最近的点
                    pq.offer(v);
                }
            }
        }
    }
    
    //获取最短路径
    public static List<Integer> getShortestPath(int start, int end) {
        List<Integer> path = new ArrayList<>();
        for (int v = end; v != start; v = prev[v]) {
            path.add(v);
        }
        path.add(start);
        Collections.reverse(path);
        return path;
    }
    
	public static void main(String[] args) {
		//建图
		int n = 5;
		
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }
		//get(点id)，add(边(终点，权重))
        g.get(0).add(new Edge(1, 10));
        g.get(0).add(new Edge(4, 3));
        g.get(1).add(new Edge(2, 2));
        g.get(1).add(new Edge(4, 4));
        g.get(2).add(new Edge(3, 9));
        g.get(3).add(new Edge(2, 7));
        g.get(3).add(new Edge(0, 6));
        g.get(4).add(new Edge(1, 1));
        g.get(4).add(new Edge(2, 8));
        g.get(4).add(new Edge(3, 2));

        showGraph();
        
        int start = 0;
        int end = 3;
        dist = new int[n];
        prev = new int[n];
        visited = new boolean[n];
        Arrays.fill(dist, INF);
        Arrays.fill(prev, -1);
        
        dijkstra(start);
        for(int i=1;i<n;i++)
        	System.out.println("Distance from " + start + " to " + i + " is " + dist[i]);
        
        List<Integer> shortestPath = getShortestPath(start, end);
        System.out.println("Shortest path: " + shortestPath.toString());
        
	}

}
